/*
EP3D is a real-time 3D planet engine , which in addition to providing 
substandard scene rendering and scene management, of course, it also 
provides some basic class libraries to build the entire virtual 
planet, or even the entire universe.

Copyright (C) 2010  Hongjiang Zhang	(zhjwyat@gmail.com)

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef EP3D_LIST_H
#define EP3D_LIST_H
#include "EP3DBase.h"
#include "EP3DMemory.h"
#include "EP3DLogger.h"
#include "EP3DFreeList.h"

namespace EP3D
{
	#define LIST_DEFAULT_RESERVE 10

	template <class T>
	class List
	{
	public:
		struct Node;

		class Iterator
		{
		public:
			Iterator()
				:m_pkNode(NULL)
			{
			}

			bool operator ==(const Iterator& other)const
			{
				return m_pkNode == other.m_pkNode;
			}

			bool operator !=(const Iterator& other) const
			{
				return m_pkNode != other.m_pkNode;
			}

			Iterator& operator ++()
			{
				LogAssert(NULL != m_pkNode);
				m_pkNode = m_pkNode->Next;
				return *this;
			}

			Iterator& operator --()
			{
				LogAssert(NULL != m_pkNode);
				m_pkNode = m_pkNode->Prev;
				return *this;
			}

			Iterator operator ++(int)
			{
				LogAssert(NULL != m_pkNode);

				Iterator pkCur(m_pkNode);
				m_pkNode = m_pkNode->Next;
				return pkCur;
			}

			Iterator operator --(int)
			{
				LogAssert(NULL != m_pkNode);
				
				Iterator pkCur(m_pkNode);
				m_pkNode = m_pkNode->Prev;
				return pkCur;
			}

			T* operator ->() const
			{
				LogAssert(NULL != m_pkNode);
				return &(m_pkNode->Value);
			}

			T& operator *() const
			{
				LogAssert(NULL != m_pkNode);
				return m_pkNode->Value;
			}

		private:
			Iterator(Node* pkNode)
				:m_pkNode(pkNode)
			{
			}

			Node* m_pkNode;

			friend class List<T>;
		};

		List()
			:m_pkHead(NULL)
			,m_pkTail(NULL)
			,m_kMemAlloctor(LIST_DEFAULT_RESERVE)
		{
		}

		~List()
		{
			Clear();
		}

		bool IsEmpty() const
		{
			return 0 == m_pkHead;
		}

		uint GetSize() const
		{
			Iterator it;
			uint uiSize = 0;
			for (it = Begin(); it != End(); it++) {
				uiSize++;
			}
			return uiSize;
		}

		void Clear()
		{
			while (m_pkTail) {
				RemoveTail();
			}
		}

		Iterator AddHead(const T& elem)
		{
			return InsertBefore(m_pkHead, elem);
		}

		Iterator AddTail(const T& elem)
		{
			return InsertAfter(m_pkTail, elem);
		}

		Iterator InsertAfter(Iterator it, const T& elem)
		{
			Node* pkNode = m_kMemAlloctor.Allocate(elem);
			if (NULL == it.m_pkNode) {
				LogAssert(NULL == m_pkHead && NULL == m_pkTail);
				m_pkHead = pkNode;
				m_pkTail = pkNode;
			}
			else {
				if (it.m_pkNode == m_pkTail) {
					m_pkTail = pkNode;
				}
				if (NULL != it.m_pkNode->Next) {
					it.m_pkNode->Next->Prev = pkNode;
				}
				pkNode->Next = it.m_pkNode->Next;
				it.m_pkNode->Next = pkNode;
				pkNode->Prev = it.m_pkNode;
			}
			return Iterator(pkNode);
		}

		Iterator InsertBefore(Iterator it, const T& elem)
		{
			Node* pkNode = m_kMemAlloctor.Allocate(elem);
			if (NULL == it.m_pkNode) {
				LogAssert(NULL == m_pkHead && NULL == m_pkTail);
				m_pkHead = pkNode;
				m_pkTail = pkNode;
			}
			else {
				if (it.m_pkNode == m_pkHead) {
					m_pkHead = pkNode;
				}
				if (NULL != it.m_pkNode->Prev) {
					it.m_pkNode->Prev->Next = pkNode;
				}
				pkNode->Prev = it.m_pkNode->Prev;
				it.m_pkNode->Prev = pkNode;
				pkNode->Next = it.m_pkNode;
			}
			return Iterator(pkNode);
		}

		T RemoveHead()
		{
			LogAssert(NULL != m_pkHead);
			return RemoveAt(m_pkHead);
		}

		T RemoveTail()
		{
			LogAssert(NULL != m_pkTail);
			return RemoveAt(m_pkTail);
		}

		T RemoveAt(Iterator it)
		{
			LogAssert(it.m_pkNode);

			Node* pkNode = it.m_pkNode;
			if (pkNode->Prev) {
				pkNode->Prev->Next = pkNode->Next;
			}
			if (pkNode->Next) {
				pkNode->Next->Prev = pkNode->Prev;
			}
			if (pkNode == m_pkHead) {
				m_pkHead = pkNode->Next;
			}
			if (pkNode == m_pkTail) {
				m_pkTail = pkNode->Prev;
			}
			pkNode->Next = NULL;
			pkNode->Prev = NULL;
			T elem = pkNode->Value;
			m_kMemAlloctor.Deallocate(pkNode);
			return elem;
		}

		T& GetHead() const
		{
			LogAssert(NULL != m_pkHead);
			return m_pkHead->Value;
		}

		T& GetTail() const
		{
			LogAssert(NULL != m_pkTail);
			return m_pkTail->Value;
		}

		Iterator Begin() const
		{
			return Iterator(m_pkHead);
		}

		Iterator End() const
		{
			return NULL;
		}

		Iterator Find(const T& elem, Iterator start) const
		{
			for (; start != End(); start++) {
				if (*start == elem) {
					return start;
				}
			}
			return NULL;
		}

	private:
		struct Node
		{
			friend class List;
			friend class Iterator;

			Node(const T& elem) :Next(0), Prev(0), Value(elem) {}

			Node* Next;
			Node* Prev;
			T Value;
		};

		Node* m_pkHead;
		Node* m_pkTail;

		typedef FreeList<Node> MemoryAlloctor;
		MemoryAlloctor	m_kMemAlloctor;
	};
}
#endif